This invention was not developed in conjunction with any Federally sponsored contract.
1. Field of the Invention
This invention relates to the arts of computer disk media, formatting of computer disks, organization of computer readable media by operating systems and device drivers, and the management of logical volumes of computer disks. In particular, this invention relates to improvements in the method for the expansion of logical volumes of disc media in the presence of plugin features in the logical volume structure.
2. Description of the Related Art
Persistent and mass data storage devices for computer systems, especially those employed in personal computers, are well known within the art. Many are disk-based, such as floppy disks, removable hard disk drives (xe2x80x9cHDDxe2x80x9d), and compact-disk read only memories (xe2x80x9cCD-ROMxe2x80x9d). FIG. 1 shows a typical personal computer system (1) architecture, wherein a CPU (2) interfaces to a variety of I/O devices such as a keyboard (3), monitor or display (5) and a mouse (4). The CPU (2) also may interface to a number of storage peripherals including CD-ROM drives (7), hard disk drives (6), and floppy drives (5). Typically, floppy disk drives interface to the CPU via Integrated Drive Electronics (xe2x80x9cIDExe2x80x9d) (8), but this interface may alternately be one of several other standard interfaces or a proprietary interface. The hard disk drives (6) and CD-ROM drives (7) may interface to the CPU (2) via an IDE or Small Computer System Interface (xe2x80x9cSCSIxe2x80x9d), as shown (9).
FIG. 2 shows a generalization of the hardware, firmware and software organization of a personal computer system (20). The hardware group (21) includes the persistent storage devices discussed supra, as well as other system hardware components such as a real-time clock, keyboard controller, display adapter, etc. A basic input/output system (xe2x80x9cBIOSxe2x80x9d) (22) provides the direct firmware control of these system components typically. An operating system (24) such as the IBM OS/2 operating system provides high level management of the system resources, including the multi-tasking or multi-threaded scheduling and prioritization of the system application programs (25). Drivers (23) provide specific high-level interface and control functions for specific hardware, such as a manufacturer and model-specific LAN interface card driver or CD-Rewritable (xe2x80x9cCD-RWxe2x80x9d) driver. This generalized view of the system also applies to systems on alternate, non-IBM-compatible platforms, such as workstations, which employ a variety of operating systems such as Microsoft Windows, UNIX or LINUX. This general organization of computer system resources and software functionality is well understood in the art.
Turning to FIG. 3, disk-based mass storage devices such as hard disk drives, floppy disks and CD-ROMS are based physically on a rotating storage platter (30). This platter may be made of flexible mylar, such as floppy disks, or more rigid platters made of aluminum, glass or plastic, such as hard disk drives and CD-ROMS. For magnetic media, one or both sides of the platter are coated with a magnetic layer capable of recording magnetic pulses from a read/write head. For optical media, data recording is made using changes in reflectivity of a band of light, which is then read by a laser-based head. Writable and Re-writable CD-ROM drives combine the technologies of magnetic disks and optical disks. In general, though, the organization of data on the disk is similar. The disk surfaces are divided into multiple concentric rings, or tracks (31). Some disk drives, such as hard disk drives, consist of multiple platters, in which case corresponding tracks on each platter are grouped into cylinders. Each track is divided into multiple sectors (32) in which data can be stored.
Turning to FIG. 4, a computer disk drive (41) is represented as an ordered collection of sectors numbered 0 through xe2x80x9cnxe2x80x9d. The very first sector on the hard drive, sector zero, contains the Master Boot Record (xe2x80x9cMBRxe2x80x9d). The MBR contains partition definitions for the rest of the disk. TABLE 1 shows a sample partial MBR.
For the disk partitioning shown in TABLE 1, the MBR is located in the first sector on side 0 at cylinder 0 sector 1. The MBR requires only one sector, but the entire track of 63 sectors is xe2x80x9cblockedxe2x80x9d for the use of the MBR, 62 sectors of side 0 cylinder 0 are left unused.
The partition table has entries in it defining two types of partitions: primary and extended. Conventional disk formatting schemes allow only one extended partition (411) to be defined. P1 (43) and P2 (44) are primary partitions. The order and locations of the primary and extended partitions may vary, but invariably there are entries in the partition table of the MBR which defines them.
The extended partition (411) is defined in the partition table in the MBR as a single partition using a single entry in the MBR partition table. Basically, this entry in the MBR just indicates to the computer operating system that inside of this extended partition can be found other partitions and partition definitions. The operating system typically assigns logical drive letters and/or logical volumes to these partitions, or groups of partitions.
In order to determine the size and location of the partitions within the extended partition, the operating system accesses the first sector of the extended partition which typically contains another boot record, known as an Extended Boot Record (xe2x80x9cEBRxe2x80x9d). The format of the EBR is similar to that of the MBR, and is also well known in the art.
FIG. 4 shows a first EBR (45), a second EBR (47), and a third EBR (49) within the extended partition (411). In practice, there may be fewer or more EBR""s within an extended partition.
Each EBR contains a partition table similar to a MBR partition table. Conventionally for computer drives commonly used in personal computers and workstations, only two entries may be in use in each EBR. One entry will define a logical partition, and the second entry acts as a link, or pointer, to the next EBR. FIG. 4 shows a pointer (412) from the second entry of the first EBR (45) to the beginning of the second EBR (47), and a similar pointer (413) from the second entry of the second EBR (47) to the beginning of the third EBR (49). The last EBR in the extended partition does not contain a pointer to a subsequent EBR, which indicates to the operating system that it is the last EBR in the extended partition. In this manner, the operating system can find and locate the definitions for an unlimited number of partitions or logical drives within the extended partition on a deterministic basis.
In each partition table entry, whether it be an EBR or an MBR, there are certain fields which indicate to the operating system the format, or file system, employed on the disk. For example, for DOS (xe2x80x9cdisk operating systemxe2x80x9d) systems, the field may indicate that the file system is File Allocation Table (xe2x80x9cFATxe2x80x9d) formatted. Or, for systems which are running IBM""s OS/2 operating system, the entry may indicate that the file system is High Performance File System (xe2x80x9cHPFSxe2x80x9d) formatted. There are a number of well-known file system formats in the industry, usually associated with the common operating systems for computers such as Microsoft""s Windows, IBM""s OS/2 and AIX, variants of UNIX, and LINUX. Using this field, the operating system may determine how to find and access data files stored within the partitions of the primary and extended partitions on the computer disk. The file system format indicator is sometimes called the xe2x80x9csystem indicatorxe2x80x9d.
IBM""s OS/2 operating system includes a function referred to as the Logical Volume Manager, or xe2x80x9cLVMxe2x80x9d. For systems without an LVM, each of the partitions that is usable by the operating system is assigned a drive letter, such as xe2x80x9cC:xe2x80x9d or xe2x80x9cF:xe2x80x9d, producing a correlating drive letter for each partition on a disk in the computer system. The process which assigns these letters is commonly known. For systems with an LVM, a drive letter may be mapped instead to a logical volume which may contain one or more partitions. The process by which partitions are combined into a single entity is known generically as xe2x80x9caggregation.xe2x80x9d Given the highly modular design of the OS/2 LVM, the functionality which performs aggregation is contained completely within a single module of the LVM program. LVM calls any module which performs aggregation an xe2x80x9caggregatorxe2x80x9d.
There are various forms of aggregation, such as drive linking, mirroring, and software Redundant Array of Independent Disks (xe2x80x9cRAIDxe2x80x9d). The OS/2 LVM allows a single level of aggregation through the use of drive linking.
The OS/2 LVM also provides xe2x80x9cfeaturesxe2x80x9d for use on logical volumes. Currently, the only feature supported is Bad Block Relocation (BBR), but this may change in the future. In general, features are intended to filter or transform data as it comes and goes to the volume. Examples of potential features would be encryption, data compression, and logical volume monitoring and statistics.
Internally, the OS/2 LVM uses a layered model. Each feature offered by the LVM for use on a volume is a layer in the LVM. The input to a layer has the same form and structure as the output from a layer. The layers being used on a volume form a stack, and I/O requests are processed from the top most layer down the stack to the bottom most layer. Currently, the bottom most layer is a special layer called the pass through layer. The top most layer is always the aggregator, which, in the current implementation, is always the drive linking layer. All of the layers in the middle of the stack represent non-aggregation features, such as Bad Block Relocation.
FIG. 5 illustrates the relationship of the layered model of the LVM and the aggregation of physical partitions into a logical volume (90). On the left, the xe2x80x9cfeature stackxe2x80x9d is shown, having a xe2x80x9cpass throughxe2x80x9d layer (97) at the bottom which interfaces directly to the disk devices or device drivers. Above the xe2x80x9cpass throughxe2x80x9d layer (97) may be a feature (96), such as Bad Block Relocation (xe2x80x9cBBRxe2x80x9d). Above the feature may be a layer of aggregation, such as drive linking (95). From the view of the feature stack model, an I/O request (98) is received at the top of the stack and propagated downwards to the pass through layer. Comparing that to a tree model of a logical volume (90), the aggregator A1 (91) corresponds to the aggregation layer (95), the feature layer (96) corresponds to the three interfaces between the aggregator A1 (91) and it""s partition definitions P1, P2, and P3 (92, 93, and 94 respectively), and the pass through layer (97) corresponds to the interfaces between the partition definitions and the actual devices or device drivers. These types of LVM structures, feature stack models, and tree models are well understood in the art, and the models can be equally well applied to logical volume management systems in other operating systems such as Hewlett Packard""s HP-UX and IBM""s AIX.
Partitions which are part of a logical volume have a special filesystem format indicator. This indicator does not correspond to any existing filesystem, and it serves to identify the partitions as belonging to a logical volume. The actual filesystem format indicator for a logical volume is stored elsewhere. Furthermore, partitions belonging to a volume have an LVM Data Area at the end of each partition in the volume. The data stored in the LVM Data Area allows the LVM to re-create the volume every time the system is booted. Thus, the LVM allows groupings of partitions to appear to the operating system as a single entity with a single drive letter assignment.
The LVM, as currently described, is a static design, with a fixed feature set and a single aggregator. Every volume which employed the aggregator could be expanded up to the limit of what the aggregator supported. Every volume which employed an aggregator also employed the same features, in the same order, on every partition in the volume. Thus, it is easy to perform an expansion as the LVM already knows what features must be applied to the partitions being added to the volume, and the LVM already knows the aggregator which will be responsible for actually adding the new partitions to the volume. Thus, the expansion process is very straight forward.
Now lets take the LVM as described and further enhance it by the inventions described in the related patents. Since we are interested in solving the general case as opposed to the specific case laid out thus far, we will further assume that LVM Features and Aggregators can be plug-in modules, and that any number of Features or Aggregators can be used to form a volume, and the Features and Aggregators associated with one volume are completely independent from those associated with another volume. The only constraint we will assume is that Features may only be applied to partitions or to the topmost aggregate in a volume. Thus, the LVM (as modified for the purposes of this example) now allows multiple levels of aggregation, and multiple features may be applied both to the partitions themselves or to the topmost aggregate that results from any aggregations carried out. Since every volume can have a different set of features and aggregators applied to it, the process to expand a volume is no longer as clear cut as it was previously.
With the new enhanced LVM as described above, we now have a very dynamic situation. Every volume can employ a different set of features and aggregators, and volumes employing the same features and aggregators do not have to apply them in the same order. Now, the LVM needs a way to determine if a volume can be expanded at all, and, if so, which aggregator will perform the expansion. The LVM also needs a way to determine which features or aggregators need to be applied to the partitions/aggregates being added to the volume, and it may even need to get user input to correctly configure the features/aggregators being applied to the partitions being added to the volume. Thus, a simple, fixed expansion method is no longer possible, but rather an adaptive method is needed.
Therefore, there exists a need in the art for an adaptive method which allows an enhanced logical volume manager (as previously described) to expand a logical volume. This method must allow the enhanced logical volume manager to determine if a logical volume is able to be expanded, what features and aggregators must be applied, in what order, to the partitions being added to the volume, and the process by which the partitions being added to the volume will be combined with the existing partitions of the volume to complete the expansion of the volume.